Many algorithms involve the processing of a continuous "stream" of data, the size of the stream usually being many times that of any on-chip cache memory which may be provided. As is well known in the art, a cache memory operates between a processor and a main memory of a computer. Data and/or instructions which are required by the process running on the processor can be held in the cache while that process runs. An access to the cache is normally much quicker than an access to main memory. If the processor does not locate a required data item or instruction in the cache memory, it directly accesses main memory to retrieve it, and the requested data item or instructions is loaded into the cache. There are various known systems for using and refilling cache memories, and in particular cache memories can exhibit advantageous characteristics in respect of pre-fetching items from main memory which are expected to be required by a processor into the cache, and aggregation of writing data items out from the cache into the main memory. Despite these advantages, the usefulness of on-chip caches for processing streams of data may be limited, since the data forming an input stream is likely to be read only once, and data in the output stream is not accessed once it has been written back to main memory. A data stream can be considered to constitute a continuous sequence of bytes of data. Streams can be classified as either an input stream or an output stream. Thus, an input stream can be considered as a continuous sequence of data items which are subject to a processing step using predefined program data to generate output data. The output data may be in the form of an output data stream or may take some other output format. An output stream of data can be considered as a continuous sequence of bytes of data which have been generated by the execution of processing steps using predefined program data. The output stream may be generated from an input stream, or may be generated directly from the program data itself.
For the reasons outlined above, streamed data generally shows poor temporal locality of reference, and can reduce the effectiveness of existing cache memories by causing the eviction of more suitable cache occupants, in particular the program data which is used to process the data stream. That data forms an ideal cache occupant because it is repeatedly accessed for processing the data stream.
The present invention seeks to allow for processing of a data stream with enhanced performance and greater predictability.